package com.lzq.leetcode.lanqiao.th12;

import java.util.Arrays;

public class s3 {

    private static int N = 2021;
    public static void main(String[] args) {


        long[] dp = new long[N+1];
        Arrays.fill(dp, Long.MAX_VALUE);

        dp[0] = 0;
        dp[1] = 1;
        for (int i=2; i<=N; i++) {
            for (int j=0; j<i; j++) {
                dp[i] = Math.min(dp[i], 1 + 2*dp[j] + 3*dp[i-1-j] + (long)j*j*(i-1-j));
            }
        }
        System.out.println(dp[N]);

    }
}
